package 剑指Offer.简单;

import Entity.TreeNode;

/**
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 4
 * @author caihe
 * @date 2022/8/28 11:04
 */
public class _54二叉搜索树的第k大节点 {

    /**
     * 二叉搜索数的特性 左节点比节点小 右节点比节点大
     * 所以使用中序遍历的话就是一个有序的链表
     * 找第k大的节点就是 中序倒叙遍历的第k个节点
     */
    int res = 0;
    int k = 0;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root, k);
        return res;
    }

    public void dfs(TreeNode root, int k) {
        if (root == null || k == 0) {
            return;
        }
        dfs(root.right, --k);
        if (k == 0) {
            res = root.val;
            return;
        }
        dfs(root.left, --k);
    }

}
